package week6th.PP9_3;

public class Sorting {

    public static <T extends Comparable<T>>
    void selectionSort(T[] data)
    {
        long startTime = System.nanoTime();
        int min;
        T temp;
        int count = 0;
        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++) {
                if (data[scan].compareTo(data[min])<0) {
                    min = scan;
                    count++;
                }
                else {
                    count++;
                }
            }

            swap(data, min, index);
        }
        long endTime = System.nanoTime();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ns");
        System.out.println("比较次数为："+count);
    }

    private static <T extends Comparable<T>>
    void swap(T[] data, int index1, int index2)
    {

        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;

    }

    public static <T extends Comparable<T>>
    void insertionSort1(T[] data)
    {
        int count=0;
        long startTime = System.nanoTime();
        for (int index = 1; index < data.length; index++)
        {
            T key = data[index];
            int position = index;

            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                data[position] = data[position-1];
                position--;
                count++;
            }
            data[position] = key;
        }
        long endTime = System.nanoTime();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ns");
        System.out.println("比较次数为："+count);
    }
    public static <T extends Comparable<? super T>> void insertionSort(T[] data) {
        long s1 = System.nanoTime();
        int count = 0;
        for (int i = 1; i < data.length; i++) {
            count++;
            T key = data[i];
            int pos = i;

            while (pos > 0 && data[pos - 1].compareTo(key) > 0) {
                data[pos] = data[pos - 1];
                pos--;
                count++;
            }

            data[pos] = key;
        }
        long s2 = System.nanoTime();
        System.out.println("插入排序," + "运行时间：" + (s2 - s1) + "ns");
        System.out.println("比较次数为" + count + "次");
    }

    public static <T extends Comparable<T>>
    void bubbleSort(T[] data)
    {
        int count=0;
        long startTime = System.nanoTime();
        int position, scan;
        T temp;

        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0) {
                    swap(data, scan, scan + 1);
                    count++;
                }
                else {
                    count++;
                }
            }
        }
        long endTime = System.nanoTime();
        System.out.println("冒泡排序，" + "运行时间：" + (endTime - startTime) + "ns");
        System.out.println("比较次数为："+count);
    }

    public static <T extends Comparable<T>>
    void bubbleSortTRA(T[] date,int i) {
        int count=0;
        long startTime = System.nanoTime();
        for (int a =i;a>=1;a=a-2){
            for (int po=date.length-1;po>=0;po--) {
                for (int scan = 0; scan < date.length - a; scan++) {
                    if (date[scan].compareTo(date[scan + a]) > 0) {
                        swap(date, scan, scan + a);
                        count++;
                    }
                    else {
                        count++;
                    }
                }
            }
        }
        long endTime = System.nanoTime();
        System.out.println("程序运行时间：" + (endTime-startTime) + "ns");
        System.out.println("比较次数为："+count);
    }

    public static <T extends Comparable<T>>
    void mergeSort(T[] data)
    {
        long startTime = System.nanoTime();
        mergeSort(data, 0, data.length - 1);
        long endTime = System.nanoTime();
        System.out.println("归并排序，" + "运行时间：" + (endTime - startTime) + "ns");
    }

    private static <T extends Comparable<T>>
    void mergeSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            int mid = (min + max) / 2;
            mergeSort(data, min, mid);
            mergeSort(data, mid+1, max);
            merge(data, min, mid, max);
        }
    }


    private static <T extends Comparable<T>>
    void merge(T[] data, int first, int mid, int last)
    {
        int count=0;
        T[] temp = (T[])(new Comparable[data.length]);

        int first1 = first, last1 = mid;
        int first2 = mid+1, last2 = last;
        int index = first1;

        while (first1 <= last1 && first2 <= last2)
        {
            if (data[first1].compareTo(data[first2]) < 0)
            {
                temp[index] = data[first1];
                first1++;
                count++;
            }
            else {
                temp[index] = data[first2];
                first2++;
                count++;
            }
            index++;
            count++;
        }

        while (first1 <= last1)
        {
            temp[index] = data[first1];
            first1++;
            index++;
            count++;
        }

        while (first2 <= last2)
        {
            temp[index] = data[first2];
            first2++;
            index++;
            count++;
        }

        for (index = first; index <= last; index++)
            data[index] = temp[index];
        System.out.println("比较的次数为："+count);
    }

    public static <T extends Comparable<T>>
    void quickSort(T[] data)
    {
        long startTime = System.nanoTime();
        quickSort(data, 0, data.length - 1);
        long endTime = System.nanoTime();
        System.out.println("快速排序，" + "运行时间：" + (endTime - startTime) + "ns");

    }

    private static <T extends Comparable<T>>
    void quickSort(T[] data, int min, int max)
    {
        if (min < max)
        {
            int indexofpartition = partition(data, min, max);
            quickSort(data, min, indexofpartition - 1);
            quickSort(data, indexofpartition + 1, max);
        }
    }

    private static <T extends Comparable<T>>
    int partition(T[] data, int min, int max)
    {
        T partitionelement;
        int left, right;
        int middle = (min + max) / 2;
        int count=0;
        partitionelement = data[middle];
        swap(data, middle, min);
        left = min;
        right = max;

        while (left < right)
        {
            while (left < right && data[left].compareTo(partitionelement) <= 0)
                left++;
            count++;
            while (data[right].compareTo(partitionelement) > 0)
                right--;
            count++;
            if (left < right)
                swap(data, left, right);
        }

        swap(data, min, right);
        System.out.println("比较的次数为："+count);
        return right;
    }

}

